RSA Signature Scheme¶

links: AC2 TOC - Digital Signatures - Index

See RSA to understand the basics.

Let $p k = (n, e)$ and $s k = (n, d)$ be ordinary RSA keys and $M = S = Z_{n}^{*}$

$RSA Signature.png$

Again as in the encrypt-decrypt cycle in RSA, the signature and verify cycle relies on the inverse feature of the two keys leveraged. Signing is done by applying a modular exponentiation to the message using the senders private key $(d, n)$ . The verification is done by applying the modular exponentiation to the signature received using the senders public key $(e, n)$ . The result of the modular exponentiation must be equal to the received signature (which indicates a valid signature).

Security¶

Textbook RSA should never be implemented like that as it's not EUF-CMA secure:

Textbook RSA is deterministic (same message always gives the same result)
Textbook RSA is multiplicative (The attacker can choose $m_{1}$ and $m_{2}$ , get signatures on them, and then construct a valid signature on the message $m_{1} m_{2}$ , even though they never got a signature on that message)

Sign the hash not the message!

Hash-and-Sign¶

Sign $h = h a s h (m)$ instead of $m \in {0, 1}^{*}$ , use a collision-resistant hash function.

RSA-SHA¶

$h a s h : {0, 1}^{*} \to {0, 1}^{256}$ for SHA-256

Standardised in PKCS#1 v1.5 (includes padding)
No proof for EUF-CMA security

RSA-FDH (RSA-PSS)¶

Standardised in PKCS#1 v2.1 as RSA-PSS (probabilistic signature scheme)

EUF-CMA secure under RSA assumption (provided that $h a s h (\cdot)$ has the properties of a random oracle)

See more details here: FDH

links: AC2 TOC - Digital Signatures - Index